% LaTeX source for textbook ``How to think like a computer scientist''
% Copyright (c)  2001  Allen B. Downey, Jeffrey Elkner, and Chris Meyers.

% Permission is granted to copy, distribute and/or modify this
% document under the terms of the GNU Free Documentation License,
% Version 1.1  or any later version published by the Free Software
% Foundation; with the Invariant Sections being "Contributor List",
% with no Front-Cover Texts, and with no Back-Cover Texts. A copy of
% the license is included in the section entitled "GNU Free
% Documentation License".

% This distribution includes a file named fdl.tex that contains the text
% of the GNU Free Documentation License.  If it is missing, you can obtain
% it from www.gnu.org or by writing to the Free Software Foundation,
% Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
%

\chapter{Stacks}

\section{Abstract data types}
\index{abstract data type|see{ADT}}
\index{ADT}
\index{encapsulation}

The data types you have seen so far are all concrete, in the
sense that we have completely specified how they are implemented.
For example, the {\tt Card} class represents a card using two
integers.  As we discussed at the time, that is not the only way
to represent a card; there are many alternative implementations.

An {\bf abstract data type}, or ADT, specifies a set of operations (or
methods) and the semantics of the operations (what they do), but it
does not specify the implementation of the operations.  That's
what makes it abstract.

Why is that useful?

\begin{itemize}

\item It simplifies the task of specifying an algorithm if you
can denote the operations you need without having to think at the
same time about how the operations are performed.

\item Since there are usually many ways to implement an ADT,
it might be useful to write an algorithm that can be used with
any of the possible implementations.

\item Well-known ADTs, such as the Stack ADT in this chapter,
are often implemented in standard libraries so they can be written
once and used by many programmers.

\item The operations on ADTs provide a common high-level language
for specifying and talking about algorithms.

\end{itemize}

When we talk about ADTs, we often distinguish the code that uses
the ADT, called the {\bf client} code, from the code that implements
the ADT, called the {\bf provider} code.

\index{client}
\index{provider}


\section{The Stack ADT}
\index{stack}
\index{collection}
\index{ADT!Stack}

In this chapter, we will look at one common ADT, the {\bf stack}.  A
stack is a collection, meaning that it is a data structure that
contains multiple elements.  Other collections we have seen include
dictionaries and lists.

\index{interface}

An ADT is defined by the operations that can be performed on it, which
is called an {\bf interface}.  The interface for a stack consists of
these operations:

\begin{description}

\item[{\tt \_\_init\_\_}:] Initialize a new empty stack.

\item[{\tt push}:] Add a new item to the stack.

\item[{\tt pop}:] Remove and return an item from the stack.  The item
that is returned is always the last one that was added.

\item[{\tt isEmpty}:] Check whether the stack is empty.

\end{description}

A stack is sometimes called a ``last in, first out'' or LIFO
data structure, because the last item added is the first to
be removed.


\section {Implementing stacks with Python lists}
\index{Stack}
\index{class!Stack}
\index{generic data structure}
\index{data structure!generic}

The list
operations that Python provides are similar to the operations that
define a stack.  The interface isn't exactly what it is supposed
to be, but we can write code to translate from the Stack ADT
to the built-in operations.

This code is called an {\bf implementation} of the Stack ADT.
In general, an implementation is a set of methods that satisfy
the syntactic and semantic requirements of an interface.

Here is an implementation of the Stack ADT that uses a Python list:

\beforeverb
\begin{verbatim}
class Stack :
  def __init__(self) :
    self.items = []

  def push(self, item) :
    self.items.append(item)

  def pop(self) :
    return self.items.pop()

  def isEmpty(self) :
    return (self.items == [])
\end{verbatim}
\afterverb
%
A {\tt Stack} object contains an attribute named {\tt items}
that is a list of items in the stack.  The initialization method
sets {\tt items} to the empty list.

To push a new item onto the stack, {\tt push} appends it onto {\tt
items}.  To pop an item off the stack, {\tt pop} uses the
homonymous\footnote{same-named} list method to remove and return the
last item on the list.

Finally, to check if the stack is empty, {\tt isEmpty} compares
{\tt items} to the empty list.

\index{veneer}

An implementation like this, in which the methods consist of simple
invocations of existing methods, is called a {\bf veneer}.  In real
life, veneer is a thin coating of good quality wood used in
furniture-making to hide lower quality wood underneath.  Computer
scientists use this metaphor to describe a small piece of code that
hides the details of an implementation and provides a simpler, or more
standard, interface.


\section{Pushing and popping}
\index{push}
\index{pop}
\index{generic data structure}
\index{data structure!generic}

A stack is a {\bf generic data structure}, which means that we can
add any type of item to it.  The following example pushes
two integers and a string onto the stack:

\beforeverb
\begin{verbatim}
>>> s = Stack()
>>> s.push(54)
>>> s.push(45)
>>> s.push("+")
\end{verbatim}
\afterverb
%
We can use {\tt isEmpty} and {\tt pop} to remove and print
all of the items on the stack:

\beforeverb
\begin{verbatim}
while not s.isEmpty() :
  print s.pop(),
\end{verbatim}
\afterverb
%
The output is {\tt + 45 54}.  In other words, we just used a stack
to print the items backward!  Granted, it's not the
standard format for printing a list, but by using a stack, it was
remarkably easy to do.

You should compare this bit of code to the implementation of {\tt
printBackward} in Section~\ref{listrecursion}.  There is a natural
parallel between the recursive version of {\tt printBackward} and the
stack algorithm here.  The difference is that {\tt printBackward} uses
the runtime stack to keep track of the nodes while it traverses the
list, and then prints them on the way back from the recursion.  The
stack algorithm does the same thing, except that it uses a {\tt Stack}
object instead of the runtime stack.



\section {Using a stack to evaluate postfix}
\index{postfix}
\index{infix}
\index{expression}

In most programming languages, mathematical expressions are
written with the operator between the two operands, as in
{\tt 1+2}.  This format is called {\bf infix}.  An alternative
used by some calculators is called {\bf postfix}.  In
postfix, the operator follows the operands, as in {\tt 1 2 +}.

The reason postfix is sometimes useful is that there is a
natural way to evaluate a postfix expression using a stack:

\begin{itemize}

\item Starting at the beginning of the expression, get one
term (operator or operand) at a time.

  \begin{itemize}

  \item If the term is an operand, push it on the stack.

  \item If the term is an operator, pop two operands off
  the stack, perform the operation on them, and push the
  result back on the stack.

  \end{itemize}

\item When you get to the end of the expression, there should
be exactly one operand left on the stack.  That operand is the
result.

\end{itemize}

\begin{quote}
{\em As an exercise, apply this algorithm to the expression
{\tt 1 2 + 3 *}.}
\end{quote}

This example demonstrates one of the advantages of postfix---there is
no need to use parentheses to control the order of operations.  To get
the same result in infix, we would have to write {\tt (1 + 2) * 3}.

\begin{quote}
{\em As an exercise, write a postfix expression that is equivalent to
{\tt 1 + 2 * 3}.}
\end{quote}


\section {Parsing}
\index{parse}
\index{token}
\index{delimiter}
\index{regular expression}

To implement the previous algorithm, we need
to be able to traverse a string and break it into operands and
operators.  This process is an example of {\bf parsing}, and the
results---the individual chunks of the string---are called {\bf
tokens}.  You might remember these words from Chapter 1.

Python provides a {\tt split} method in both the {\tt string} and {\tt
re} (regular expression) modules. The function {\tt string.split}
splits a string into a list using a single character as a {\bf delimiter}.
For example:

\beforeverb
\begin{verbatim}
>>> import string
>>> string.split("Now is the time"," ")
['Now', 'is', 'the', 'time']
\end{verbatim}
\afterverb
%
In this case, the delimiter is the space character, so the string
is split at each space.

The function {\tt re.split} is more powerful, allowing us to
provide a regular expression instead of a delimiter.
A regular expression is a way of specifying a set of strings.
For example, \verb+[A-z]+ is the set of all letters and
\verb+[0-9]+ is the set of all digits.  The \verb+^+ operator
negates a set, so \verb+[^0-9]+ is the set of every character that
is not a digit, which is exactly the set we want to use to
split up postfix expressions:

\beforeverb
\begin{verbatim}
>>> import re
>>> re.split("([^0-9])", "123+456*/")
['123', '+', '456', '*', '', '/', '']
\end{verbatim}
\afterverb
%
Notice that the order of the
arguments is different from {\tt string.split}; the delimiter comes
before the string.

The resulting list includes the operands {\tt 123} and {\tt 456} and
the operators {\tt *} and {\tt /}.  It also includes two empty
strings that are inserted as ``phantom operands,'' whenever an
operator appears without a number before or after it.


\section {Evaluating postfix}

To evaluate a postfix expression, we will use the parser from
the previous section and the algorithm from the section before that.
To keep things simple, we'll start with an evaluator that
only implements the operators {\tt +} and {\tt *}:

\adjustpage{-3}
\pagebreak

\beforeverb
\begin{verbatim}
def evalPostfix(expr):
  import re
  tokenList = re.split("([^0-9])", expr)
  stack = Stack()
  for token in tokenList:
    if  token == '' or token == ' ':
      continue
    if  token == '+':
      sum = stack.pop() + stack.pop()
      stack.push(sum)
    elif token == '*':
      product = stack.pop() * stack.pop()
      stack.push(product)
    else:
      stack.push(int(token))
  return stack.pop()
\end{verbatim}
\afterverb
%
The first condition takes care of spaces and empty strings.  The next
two conditions handle operators. We assume, for now, that anything
else must be an operand.  Of course, it would be better to check for
erroneous input and report an error message, but we'll get to that
later.

Let's test it by evaluating the postfix form of {\tt (56+47)*2}:

\beforeverb
\begin{verbatim}
>>> print evalPostfix ("56 47 + 2 *")
206
\end{verbatim}
\afterverb
%
That's close enough.


\section {Clients and providers}
\index{encapsulation}
\index{ADT}

One of the fundamental goals of an ADT is to separate the
interests of the provider, who writes the code that implements
the ADT, and the client, who uses the ADT.
The provider only has to worry
about whether the implementation is correct---in accord
with the specification of the ADT---and not how it will be used.

Conversely, the client {\em assumes} that the implementation of the
ADT is correct and doesn't worry about the details.  When you
are using one of Python's built-in types, you have the luxury
of thinking exclusively as a client.

Of course, when you implement an ADT, you also have
to write client code to test it.  In that case, you play both
roles, which can be confusing.  You should make some effort
to keep track of which role you are playing at any moment.


\section{Glossary}
\index{ADT}
\index{client}
\index{provider}
\index{infix}
\index{postfix}
\index{parse}
\index{token}
\index{delimiter}

\begin{description}

\item[abstract data type (ADT):]  A data type (usually a collection
of objects) that is defined by a set of operations but that can
be implemented in a variety of ways.

\item[interface:] The set of operations that define an ADT.

\item[implementation:] Code that satisfies the syntactic and semantic
requirements of an interface.

\item[client:]  A program (or the person who wrote it) that uses an ADT.

\item[provider:] The code (or the person
who wrote it) that implements an ADT.

\item[veneer:]  A class definition that implements an ADT with
method definitions that are invocations of other methods, sometimes
with simple transformations.  The veneer does no significant work,
but it improves or standardizes the interface seen by the client.

\item[generic data structure:] A kind of data structure that can
contain data of any type.

\item[infix:]  A way of writing mathematical expressions with the
operators between the operands.

\item[postfix:]  A way of writing mathematical expressions with the
operators after the operands.

\item[parse:]  To read a string of characters or tokens and analyze
its grammatical structure.

\item[token:]  A set of characters that are treated as a unit for
purposes of parsing, such as the words in a natural language.

\item[delimiter:]  A character that is used to separate tokens,
such as punctuation in a natural language.

\end{description}
